package arithmetic.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * 字符串处理章节
 */
public class StringTest {


    /**
     * LeetCode-76
     * 最小覆盖字串
     *  使用滑动窗口
     *
     */



    /**
     * LeetCode-3无重复字符的最长子串
     * 给定一个字符串s,请你找出其中不含有重复字符的最长字串的长度
     *  ---滑动窗口的考察
     */
    public static int lengthOfLongestSubstring(String s){
        Set<Character> set = new HashSet<>();//Hash集合,记录每个字符是否出现过
        int n = s.length();
        int rk = -1; //右指针 初始值为-1
        int ans = 0; //最长子串的长度
        //遍历字符串,i代表左指针
        for (int i = 0; i < n; i++){
            if(i != 0){
                //左指针向右移动一格,移除一个字符
                set.remove(s.charAt(i - 1));
            }
            //i = 0;rk + 1 =0,从字符串第0个字符开始
            while (rk + 1 < n && !set.contains(s.charAt(rk+1))){
                set.add(s.charAt(rk + 1));
                rk++;
            }
            //从第i到rk个字符是一个极长的无重复字符字串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    /**
     * LeetCode-151
     * 翻转字符串里的单词
     *
     * 给你一个字符串S,逐个翻转字符串中的所有单词
     * 输入:S="the sky is blue";
     * 输出:"blue is sky the"
     *
     * 使用倒序的方式
     */
    public String reverseWords(String s){
        char[] charArray = s.toCharArray();
        int left = 0;
        int right = charArray.length - 1;
        //先排除字符串的前后空格
        while (charArray[left] == ' ') left++;
        while (charArray[right] == ' ') right--;
        StringBuilder sb = new StringBuilder();
        //开始倒序遍历字符串
        while (left < right){
            int index = right;
            while (index >= left && charArray[index] != ' '){
                index--;
            }
            //遇见单词前的空格,取出单词,单词的范围就是index + 1 ~ right
            for (int i = index + 1;i <= right; i++){
                sb.append(charArray[i]);
            }
            if(index > left){
                sb.append(' ');
            }
            //单词之间可能有多个空格,排除
            while (index >= left && charArray[index] == ' '){
                index--;
            }
            //遇见了新单词
            right = index;
        }
        return sb.toString();
    }

    /**
     * LeetCode-165
     * 比较版本号
     *  版本号由一个或多个修订号组成,各修订号由一个','连接,每个修订号由多为数字组成,可能包含前导0
     *
     */
    public int compareVersion(String version1, String version2){
        int i = 0, j = 0;
        int n = version1.length(), m = version2.length();
        while (i < n || j < m){
            int num1 = 0, num2 = 0;
            while (i < n && version1.charAt(i) != '.'){
                num1 = num1 * 10 + version1.charAt(i++) - '0';
            }
            while (j < m && version2.charAt(j) != '.'){
                num2 = num2 * 10 + version2.charAt(j++) - '0';
            }
            if (num1 > num2){
                return 1;
            }else if (num1 < num2){
                return -1;
            }else {
                i++;
                j++;
            }
        }
        return 0;
    }

    /**
     * LeetCode-240
     * 搜索二维矩阵II
     *  ---矩阵列满足从小到大排列,行满足从小到大排列
     *
     *  时间复杂度O(m+n)
     */
    public boolean searchMatrix(int[][] matrix, int target){
        if (matrix == null){
            return false;
        }
        //获取矩阵行和列小标的最大值
        int cols = matrix[0].length - 1;//列
        int rows = matrix.length - 1;//行
        if(target > matrix[rows][cols]){
            return false;
        }
        int currCol = cols;//表示从矩阵的右上角开始比较
        int currRow = 0;
        while (currCol >= 0 && currRow <= rows){
            if(target == matrix[currRow][currCol]){
                return true;
            }else if(target < matrix[currRow][currCol]){
                currCol--;
            }else {
                currRow++;
            }
        }
        return false;
    }

}
